// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
)

// 定义一个表示二维平面点的结构体
type Point struct {
	x float64
	y float64
}

// 计算两个点之间的距离
func distance(p1, p2 Point) float64 {
	dx := p1.x - p2.x
	dy := p1.y - p2.y
	return math.Sqrt(dx*dx + dy*dy)
}

// KNN算法函数，给定k值、点集和输入点，返回输入点所属的类别
func KNN(k int, points []Point, input Point) string {
	//创建一个数组保存点集中每个点到输入点的距离
	distances := make([]float64, len(points))
	for i, point := range points {
		distances[i] = distance(point, input)
	}

	//创建一个数组保存点集中每个点的索引
	indices := make([]int, len(points))
	for i := range indices {
		indices[i] = i
	}

	//按距离的升序对距离和索引进行排序，以便找到k个最近邻点
	for i := 0; i < len(distances); i++ {
		for j := i + 1; j < len(distances); j++ {
			if distances[i] > distances[j] {
				distances[i], distances[j] = distances[j], distances[i]
				indices[i], indices[j] = indices[j], indices[i]
			}
		}
	}

	//统计每个类在K个最近邻点中出现的频率
	classCounts := make(map[string]int)
	for i := 0; i < k; i++ {
		classCounts[fmt.Sprintf("Class %d", indices[i])]++
	}

	//找到频率最高的类
	maxCount := 0
	var maxClass string
	for class, count := range classCounts {
		if count > maxCount {
			maxCount = count
			maxClass = class
		}
	}

	return maxClass
}

// 创建点集和输入点，调用KNN函数计算输入点的类别，并打印结果
func main() {
	points := []Point{
		{2, 2},
		{4, 3},
		{6, 1},
		{8, 3},
		{10, 4},
	}
	input := Point{6, 4}

	//调用KNN函数，找到输入点的类别
	fmt.Println(KNN(3, points, input))
}

//$ go run kNN.go
//Class 1
